#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++)
            sum += nums[i];

        if (sum % 2 != 0) return false;
        int V = sum / 2;
        vector<vector<int>> dp(len + 1, vector<int>(V + 1, 0));
        for (int j = 1; j <= V; j++)
            dp[0][j] = -1;

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != -1) {
                    dp[i][j] = true;
                }
            }
        }
        return (dp[len][V] == -1) ? 0 : dp[len][V];
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++)
            sum += nums[i];

        if (sum % 2 != 0) return false;
        int V = sum / 2;
        vector<vector<bool>> dp(len + 1, vector<bool>(V + 1, 0));

        for (int i = 0; i <= len; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]] != false) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[len][V];
    }
};

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++)
            sum += nums[i];

        if (sum % 2 != 0) return false;
        int V = sum / 2;
        vector<bool> dp(V + 1);

        dp[0] = true;

        for (int i = 1; i <= len; i++) {
            for (int j = V; j >= nums[i - 1]; j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];

            }
        }

        return dp[V];
    }
};